<html>
<head><meta charset="utf-8"><title>In-compiler range calculations · t-compiler/wg-mir-opt · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/index.html">t-compiler/wg-mir-opt</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html">In-compiler range calculations</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="209549147"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209549147" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209549147">(Sep 09 2020 at 18:25)</a>:</h4>
<p>Was just discussing this in <a class="stream" data-stream-id="213817" href="/#narrow/stream/213817-t-lang">#t-lang</a> as an offshoot of discussing ternary operands, and was wondering just how much it’d take to implement (Presumably, more than is possible for me at least!)<br>
It’d presumably need to store additional data (range data) on MIR constructs and where and how those could be stored is unknown to me. Actually range checking isn’t too difficult for simpler math, but could get complicated for functions, as they may need annotated with range information. Anyone have a better idea of what’d be involved in an implementation?</p>



<a name="209549291"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209549291" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Notification Bot <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209549291">(Sep 09 2020 at 18:27)</a>:</h4>
<p>This topic was moved here from <a class="stream-topic" data-stream-id="131828" href="/#narrow/stream/131828-t-compiler/topic/In-compiler.20range.20calculations">#t-compiler &gt; In-compiler range calculations</a> by <span class="user-mention silent" data-user-id="116122">simulacrum</span></p>



<a name="209549300"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209549300" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209549300">(Sep 09 2020 at 18:27)</a>:</h4>
<p>I think an almost-hard requirement is probably some form of inlining, which has historically been Hard, though there's been some recent progress I think.</p>



<a name="209549675"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209549675" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209549675">(Sep 09 2020 at 18:30)</a>:</h4>
<p>What would inlining be for in this case? (I’m still fairly new to working on rustc.)</p>



<a name="209549783"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209549783" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209549783">(Sep 09 2020 at 18:31)</a>:</h4>
<p>Well, it's a more general thing -- without inlining, even something like <code>vec[x]</code> passes through 3-4 levels of indirection, first the deref to a slice, then the index trait on slices -- some of that is a compiler-implemented thing, some isn't</p>



<a name="209549848"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209549848" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209549848">(Sep 09 2020 at 18:32)</a>:</h4>
<p>but until you "pull that in" you're unlikely to be able to realize "oh that needs <code>x</code> in bounds" without heuristics or something</p>



<a name="209550083"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550083" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550083">(Sep 09 2020 at 18:34)</a>:</h4>
<p>The original reason this was brought up is to make <code>match</code> smarter about if all possible values have been checked. Is that goal even achievable from MIR?</p>



<a name="209550126"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550126" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550126">(Sep 09 2020 at 18:34)</a>:</h4>
<p>Well, match checking for full coverage of the input range happens entirely at the MIR level</p>



<a name="209550135"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550135" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550135">(Sep 09 2020 at 18:34)</a>:</h4>
<p>So "yes"</p>



<a name="209550177"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550177" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550177">(Sep 09 2020 at 18:35)</a>:</h4>
<p>the harder part there is usually deciding how much we want to be able to infer about the input range -- right now it's purely just the type, nothing else</p>



<a name="209550362"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550362" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550362">(Sep 09 2020 at 18:36)</a>:</h4>
<p>I assume a partial implementation of range checks would be doable without inlining. Handling simple math on the type is easy, there’s ways to calculate the range of outputs possible from most operations, and it’d make a good first step.</p>



<a name="209550388"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550388" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550388">(Sep 09 2020 at 18:36)</a>:</h4>
<p>Sure, yes, to some extent</p>



<a name="209550533"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550533" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550533">(Sep 09 2020 at 18:38)</a>:</h4>
<p>The implementation of the simple cases is not <em>too</em> hard. The language-level guarantees it implies is a bit harder.</p>
<p>For example, does introducing a binding break it? e.g., <code>match a &amp; 1</code> requires just 0 and 1, perhaps, but <code>let b = a &amp; 1; match b { ... }</code> now requires everything in the type again? That sort of decision needs to be made.</p>



<a name="209550575"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550575" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550575">(Sep 09 2020 at 18:38)</a>:</h4>
<p>and whether we're okay with some cases getting covered and others not, and to what extent that stabilizes a very particular implementation</p>



<a name="209550631"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550631" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550631">(Sep 09 2020 at 18:39)</a>:</h4>
<p>An early implementation could be made and feature flagged. Ideally, as much as is sane could be handled, so supporting simple math and bindings would be a good step 1</p>



<a name="209550703"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550703" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550703">(Sep 09 2020 at 18:39)</a>:</h4>
<p>As for stabilizing a particular implementation, I imagine that could be argued until the heat death of the universe.</p>



<a name="209550980"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209550980" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209550980">(Sep 09 2020 at 18:42)</a>:</h4>
<p>Being able to track this information as much as possible is also a good step toward some useful compiler optimizations, like partially lifting bounds check omission into a MIR pass (and letting LLVM continue to catch any omittable checks that get missed)</p>



<a name="209551370"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209551370" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209551370">(Sep 09 2020 at 18:45)</a>:</h4>
<p>Implementing range computation internally with no effect on UI is always an option to start.</p>



<a name="209551615"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209551615" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209551615">(Sep 09 2020 at 18:47)</a>:</h4>
<p>There's a difference between optimizations and match checking in that match checking is "language spec" territory since it's a stable detail visible to users. But yes, largely seems fine.</p>



<a name="209552103"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209552103" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209552103">(Sep 09 2020 at 18:51)</a>:</h4>
<p>So what might be involved with implementing a simpler version of range computation? There would need to be some way to attach range data to bindings.</p>



<a name="209555445"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209555445" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209555445">(Sep 09 2020 at 19:17)</a>:</h4>
<p>If you want to expose this in the type system, you'd have to limit it to builtin operations, which do not require inlining</p>



<a name="209555538"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209555538" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209555538">(Sep 09 2020 at 19:18)</a>:</h4>
<p>If it's just for optimization, there was a recent discussion on doing value range analysis as a dataflow analysis</p>



<a name="209555600"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209555600" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209555600">(Sep 09 2020 at 19:18)</a>:</h4>
<p>That was somewhere here: <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation/near/208654443">https://rust-lang.zulipchat.com/#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Flow-sensitive.20MIR.20const-propagation/near/208654443</a></p>



<a name="209555818"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209555818" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209555818">(Sep 09 2020 at 19:20)</a>:</h4>
<p>And you get to the user-specified range types, which are much-clamored for.</p>



<a name="209555878"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209555878" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209555878">(Sep 09 2020 at 19:20)</a>:</h4>
<p>e.g. <code>IntegerBetween&lt;5, 10&gt;</code>.</p>



<a name="209565112"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209565112" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209565112">(Sep 09 2020 at 20:31)</a>:</h4>
<p>I think that for it to be a language change to something like <code>match</code> checking (and whether you need a <code>_=&gt;</code> arm), I'd expect it to be something that is part of the type of what went into match, not just a value-range-analysis pass.</p>



<a name="209565309"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209565309" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209565309">(Sep 09 2020 at 20:33)</a>:</h4>
<p>But certainly linting on things like <code>match x &amp; 3 { 5 =&gt; </code> would be cool -- that's a QoI question, not a spec one.</p>



<a name="209565582"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209565582" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209565582">(Sep 09 2020 at 20:35)</a>:</h4>
<p>with <a href="https://github.com/rust-lang/rust/pull/76044">https://github.com/rust-lang/rust/pull/76044</a> we can now actuall implement such dataflow analyses</p>



<a name="209565676"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209565676" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209565676">(Sep 09 2020 at 20:36)</a>:</h4>
<p>I don't have the capacity to do such an impl right now, but I can mentor and iirc <span class="user-mention" data-user-id="212698">@Félix Fischer</span> was interested in working on something like that</p>



<a name="209572280"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209572280" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209572280">(Sep 09 2020 at 21:40)</a>:</h4>
<p>I’m strongly interested too which is why I posed the question</p>



<a name="209580065"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209580065" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jubilee <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209580065">(Sep 09 2020 at 23:15)</a>:</h4>
<p>The range should be expressible using existing range syntax &lt;/opinion&gt;</p>



<a name="209605915"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209605915" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209605915">(Sep 10 2020 at 07:54)</a>:</h4>
<p>Thanks for the ping, <span class="user-mention" data-user-id="124288">@oli</span> <br>
I'm however lying low for now. Uni hasn't responded to me and I'm also having a bad brain couple of weeks. I'm saving on energy so that I can take care of that stuff :3</p>



<a name="209605966"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209605966" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209605966">(Sep 10 2020 at 07:54)</a>:</h4>
<p>The dataflow analysis looks so goooood tho <span aria-label="heart" class="emoji emoji-2764" role="img" title="heart">:heart:</span>️</p>



<a name="209606121"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209606121" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209606121">(Sep 10 2020 at 07:56)</a>:</h4>
<p><span class="user-mention" data-user-id="277614">@Braden Nelson</span> if/and when you end up working on this, please ping me at your PR so that I can keep myself up-to-date with it. I'm glad you're interested in these things! It's a super cool part of the compiler <span aria-label="blush" class="emoji emoji-1f60a" role="img" title="blush">:blush:</span></p>



<a name="209606254"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209606254" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209606254">(Sep 10 2020 at 07:58)</a>:</h4>
<p>PS: oli is an amazing mentor. If you work with them, you'll definitely have a blast :)</p>



<a name="209608529"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209608529" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209608529">(Sep 10 2020 at 08:25)</a>:</h4>
<p>range analysis has a lot of applications but is not trivial, the literature often describes them over infinite lattices so you need widening to ensure termination, narrowing to help precision, ranges are actually symbolic, inlining is mostly a matter of precision (for the same reason they can be inter-procedural analyses) in context-sensitivity, and it more often than not I'd say takes advantage of at least SSA form (and e-SSA has been invented to again help with precision IIRC), and that's not mentioning the implementation challenges of analysis speed vs precision. I'm not saying this to deter anyone from working on this, it sounds super fun :)</p>



<a name="209608574"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209608574" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209608574">(Sep 10 2020 at 08:26)</a>:</h4>
<p>let me get you a paper showing at least an overview and some implementation talk</p>



<a name="209608655"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209608655" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209608655">(Sep 10 2020 at 08:26)</a>:</h4>
<p>say, <a href="ftp://nozdr.ru/biblio/kolxoz/Cs/CsLn/Programming%20Languages,%2016%20conf.,%20SBLP%202012%20(LNCS7554,%20Springer,%202012)(ISBN%209783642331817)(O)(173s)_CsLn_.pdf#page=50">this</a> and the authors (at least Pereira) have published other papers on the subject; or maybe the ABCD paper</p>



<a name="209608824"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209608824" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209608824">(Sep 10 2020 at 08:28)</a>:</h4>
<p>if the goal is just match checking, maybe some of Luc Maranget's papers could be useful (I'm not sure if that's the one varkor used in their initial overlap and missing arms implementation) say <a href="http://moscova.inria.fr/~maranget/papers/warn/index.html">this one</a> is well-known but maybe not exactly about checking on ranges (but could be interesting wrt our match checking being quadratic)</p>



<a name="209609195"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209609195" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209609195">(Sep 10 2020 at 08:32)</a>:</h4>
<p>if it's bounds check elimination, which I believe we'll really need to do at some point, because we're the "only ones" with bounds checks in optimized code (in loops, of the well-known languages using LLVM), we'd surely have to detect and model loops and induction variables and more, there's some nice information in Muchnick's book (which I like to believe is <span class="user-mention" data-user-id="118594">@ecstatic-morse</span> bedside reading :)</p>



<a name="209668370"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209668370" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209668370">(Sep 10 2020 at 15:58)</a>:</h4>
<p>It's more of a bathroom reader: A few paragraphs a day <span aria-label="smile" class="emoji emoji-1f642" role="img" title="smile">:smile:</span></p>



<a name="209677609"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209677609" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209677609">(Sep 10 2020 at 17:02)</a>:</h4>
<p>perhaps GCC's Project Ranger is of interest? <a href="https://gcc.gnu.org/pipermail/gcc/2020-July/233235.html">https://gcc.gnu.org/pipermail/gcc/2020-July/233235.html</a><br>
in a recent internal talk, Andrew mentioned that it's not strictly tied to GCC IR, could be integrated into other toolchains</p>



<a name="209679084"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209679084" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209679084">(Sep 10 2020 at 17:13)</a>:</h4>
<p><span class="user-mention" data-user-id="124288">@oli</span> I'm fairly interested in doing this. Mentoring would be helpful, but really once I figure out the internal structure/design for how I should actually attempt to do this, I should be pretty well off on my own with just the occasional bunch of questions.</p>



<a name="209679170"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209679170" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209679170">(Sep 10 2020 at 17:14)</a>:</h4>
<p>I imagine I should start with opening an issue and self-assigning?</p>



<a name="209679447"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209679447" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209679447">(Sep 10 2020 at 17:16)</a>:</h4>
<p>Yea, let's collect the info in an issue, just ping me on the issue when you open it and I'll write something up</p>



<a name="209680018"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209680018" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209680018">(Sep 10 2020 at 17:22)</a>:</h4>
<p><span class="user-mention" data-user-id="124288">@oli</span> what/which issue layout should I use? Cut down version of the Tracking Issue template?</p>



<a name="209680080"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209680080" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209680080">(Sep 10 2020 at 17:22)</a>:</h4>
<p>yea that sounds good</p>



<a name="209682465"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209682465" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Braden Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209682465">(Sep 10 2020 at 17:41)</a>:</h4>
<p><span class="user-mention" data-user-id="124288">@oli</span> Github username?</p>



<a name="209682500"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/209682500" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#209682500">(Sep 10 2020 at 17:41)</a>:</h4>
<p>oli-obk</p>



<a name="215033334"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/215033334" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dániel Buga <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#215033334">(Oct 29 2020 at 21:52)</a>:</h4>
<p>Is anybody working on this currently? I'm interested in the topic and I'm trying to work out an MVP as practice and to see if I understand the concepts correctly. Probably not the best analysis to get into as a beginner, but a fun one to read and think about <span aria-label="smile" class="emoji emoji-1f642" role="img" title="smile">:smile:</span></p>



<a name="215063908"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/215063908" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#215063908">(Oct 30 2020 at 07:50)</a>:</h4>
<p>I think <span class="user-mention" data-user-id="212698">@Félix Fischer</span> wants to/is work/ing on this as part of a university project</p>



<a name="215065791"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/215065791" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#215065791">(Oct 30 2020 at 08:21)</a>:</h4>
<p>Yup!</p>



<a name="215065881"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler%20range%20calculations/near/215065881" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/In-compiler.20range.20calculations.html#215065881">(Oct 30 2020 at 08:23)</a>:</h4>
<p>I want to work on it, and although I've been slow to start it, I've been given the thumbs up by uni so I think I'll might start tackling it in the next few months</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>